package org.example.sword2offer.primary;

/**
 * @author: lynn
 * @Descript: 删除链表中重复的结点
 * 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
 * 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
 * @date: 2021/3/24 0:17
 * @version: 1.0
 */
public class Q55_DeleteDuplicationNode {
    public static void main(String[] args) {
        ListNode listNode=new ListNode(5);
        listNode.next=new ListNode(4);
        listNode.next.next=new ListNode(4);
        listNode.next.next.next=new ListNode(3);
        listNode.next.next.next.next=new ListNode(2);
        System.out.println(deleteDuplication(listNode));
    }

    /**
     * 如果某个结点的后继结点与其重复，那么删除该结点的一串连续重复的结点之后如何删除该结点本身，这就要求我们需要保留当前遍历结点的前驱指针。
     * 但是如果从头结点开始就出现一连串的重复呢？我们又如何删除删除头结点，因此我们需要新建一个辅助结点作为头结点的前驱结点。
     * 在遍历过程中如何区分当前结点是不重复的结点，还是在删除了它的若干后继结点之后最后也要删除它本身的重复结点？
     * 这就需要我们使用一个布尔变量记录是否开启了删除模式（deleteMode）
     */
    public static ListNode deleteDuplication(ListNode pHead) {
        if (pHead==null){
            return null;
        }
        ListNode node=new ListNode(Integer.MIN_VALUE); //虚拟头结点
        node.next=pHead;
        ListNode pre = node, p = pHead; //为什么老喜欢拷贝一份出来???
        Boolean deleteMode=false;
        while (p!=null){
            if (p.next != null && p.next.val == p.val){
                p=p.next; //已经变了
                deleteMode=true;
            }
            else if (deleteMode){
                pre.next = p.next;
                //p变成下一个节点，相当于直接绕过去两个了
                p = p.next;
                deleteMode = false;
            }else {
                //继续往下
                pre=p;
                p=p.next;
            }
        }
        return node.next;
    }

    private  static class ListNode{
        int val;
        ListNode next;
        public ListNode(int val){
            this.val=val;
        }
    }

}
